{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在红黑树中，用巧妙的方法使用了2个结点解决了3个结点的问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 平衡查找树之红黑树（Red-Black Tree）\n",
    "\n",
    "红黑树的定义\n",
    "\n",
    "       红黑树是一种具有红色和黑色链接的平衡查找树，同时满足： \n",
    "             ① 红色节点向左倾斜 ；\n",
    "             ②一个节点不可能有两个红色链接；\n",
    "             ③整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同。\n",
    "\n",
    "红黑树的性质\n",
    "\n",
    "     整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同（2-3树的第2）性质，从根节点到叶子节点的距离都相等）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "    最坏的情况就是，红黑树中除了最左侧路径全部是由3-node节点组成，即红黑相间的路径长度是全黑路径长度的2倍。 \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    性质1：每个节点要么是黑色，要么是红色。\n",
    "    性质2：根节点是黑色。\n",
    "    性质3：每个叶子节点（NIL）是黑色。\n",
    "    性质4：每个红色结点的两个子结点一定都是黑色。\n",
    "    性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。\n",
    "\n",
    "红黑树并不是一个完美平衡二叉查找树，从图1可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/红黑树.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 平衡\n",
    "\n",
    "前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。\n",
    "\n",
    "    左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。\n",
    "    右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。\n",
    "    变色：结点的颜色由红变黑或由黑变红。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK!\n"
     ]
    }
   ],
   "source": [
    "#红黑树\n",
    "from random import randint\n",
    "\n",
    "RED = 'red'\n",
    "BLACK = 'black'\n",
    "\n",
    "class RBT:\n",
    "    def __init__(self):\n",
    "       # self.items = []\n",
    "        self.root = None\n",
    "        self.zlist = []\n",
    "\n",
    "    def LEFT_ROTATE(self, x):\n",
    "        # x是一个RBTnode\n",
    "        y = x.right\n",
    "        if y is None:\n",
    "            # 右节点为空，不旋转\n",
    "            return\n",
    "        else:\n",
    "            beta = y.left\n",
    "            x.right = beta\n",
    "            if beta is not None:\n",
    "                beta.parent = x\n",
    "\n",
    "            p = x.parent\n",
    "            y.parent = p\n",
    "            if p is None:\n",
    "                # x原来是root\n",
    "                self.root = y\n",
    "            elif x == p.left:\n",
    "                p.left = y\n",
    "            else:\n",
    "                p.right = y\n",
    "            y.left = x\n",
    "            x.parent = y\n",
    "\n",
    "    def RIGHT_ROTATE(self, y):\n",
    "        # y是一个节点\n",
    "        x = y.left\n",
    "        if x is None:\n",
    "            # 右节点为空，不旋转\n",
    "            return\n",
    "        else:\n",
    "            beta = x.right\n",
    "            y.left = beta\n",
    "            if beta is not None:\n",
    "                beta.parent = y\n",
    "\n",
    "            p = y.parent\n",
    "            x.parent = p\n",
    "            if p is None:\n",
    "                # y原来是root\n",
    "                self.root = x\n",
    "            elif y == p.left:\n",
    "                p.left = x\n",
    "            else:\n",
    "                p.right = x\n",
    "            x.right = y\n",
    "            y.parent = x\n",
    "\n",
    "    def INSERT(self, val):\n",
    "\n",
    "        z = RBTnode(val)\n",
    "        y = None\n",
    "        x = self.root\n",
    "        while x is not None:\n",
    "            y = x\n",
    "            if z.val < x.val:\n",
    "                x = x.left\n",
    "            else:\n",
    "                x = x.right\n",
    "\n",
    "        z.PAINT(RED)\n",
    "        z.parent = y\n",
    "\n",
    "        if y is None:\n",
    "            # 插入z之前为空的RBT\n",
    "            self.root = z\n",
    "            self.INSERT_FIXUP(z)\n",
    "            return\n",
    "\n",
    "        if z.val < y.val:\n",
    "            y.left = z\n",
    "        else:\n",
    "            y.right = z\n",
    "\n",
    "        if y.color == RED:\n",
    "            # z的父节点y为红色，需要fixup。\n",
    "            # 如果z的父节点y为黑色，则不用调整\n",
    "            self.INSERT_FIXUP(z)\n",
    "\n",
    "        else:\n",
    "            return\n",
    "\n",
    "    def INSERT_FIXUP(self, z):\n",
    "        # case 1:z为root节点\n",
    "        if z.parent is None:\n",
    "            z.PAINT(BLACK)\n",
    "            self.root = z\n",
    "            return\n",
    "\n",
    "        # case 2:z的父节点为黑色\n",
    "        if z.parent.color == BLACK:\n",
    "            # 包括了z处于第二层的情况\n",
    "            # 这里感觉不必要啊。。似乎z.parent为黑色则不会进入fixup阶段\n",
    "            return\n",
    "\n",
    "        # 下面的几种情况，都是z.parent.color == RED:\n",
    "        # 节点y为z的uncle\n",
    "        p = z.parent\n",
    "        g = p.parent  # g为x的grandpa\n",
    "        if g is None:\n",
    "            return\n",
    "            #   return 这里不能return的。。。\n",
    "        if g.right == p:\n",
    "            y = g.left\n",
    "        else:\n",
    "            y = g.right\n",
    "\n",
    "        # case 3-0:z没有叔叔。即：y为NIL节点\n",
    "        # 注意，此时z的父节点一定是RED\n",
    "        if y == None:\n",
    "            if z == p.right and p == p.parent.left:\n",
    "                # 3-0-0:z为右儿子,且p为左儿子，则把p左旋\n",
    "                # 转化为3-0-1或3-0-2的情况\n",
    "                self.LEFT_ROTATE(p)\n",
    "                p, z = z, p\n",
    "                g = p.parent\n",
    "            elif z == p.left and p == p.parent.right:\n",
    "                self.RIGHT_ROTATE(p)\n",
    "                p, z = z, p\n",
    "\n",
    "            g.PAINT(RED)\n",
    "            p.PAINT(BLACK)\n",
    "            if p == g.left:\n",
    "                # 3-0-1:p为g的左儿子\n",
    "                self.RIGHT_ROTATE(g)\n",
    "            else:\n",
    "                # 3-0-2:p为g的右儿子\n",
    "                self.LEFT_ROTATE(g)\n",
    "\n",
    "            return\n",
    "\n",
    "        # case 3-1:z有黑叔\n",
    "        elif y.color == BLACK:\n",
    "            if p.right == z and p.parent.left == p:\n",
    "                # 3-1-0:z为右儿子,且p为左儿子,则左旋p\n",
    "                # 转化为3-1-1或3-1-2\n",
    "                self.LEFT_ROTATE(p)\n",
    "                p, z = z, p\n",
    "            elif p.left == z and p.parent.right == p:\n",
    "                self.RIGHT_ROTATE(p)\n",
    "                p, z = z, p\n",
    "\n",
    "            p = z.parent\n",
    "            g = p.parent\n",
    "\n",
    "            p.PAINT(BLACK)\n",
    "            g.PAINT(RED)\n",
    "            if p == g.left:\n",
    "                # 3-1-1:p为g的左儿子，则右旋g\n",
    "                self.RIGHT_ROTATE(g)\n",
    "            else:\n",
    "                # 3-1-2:p为g的右儿子，则左旋g\n",
    "                self.LEFT_ROTATE(g)\n",
    "\n",
    "            return\n",
    "\n",
    "\n",
    "        # case 3-2:z有红叔\n",
    "        # 则涂黑父和叔，涂红爷，g作为新的z，递归调用\n",
    "        else:\n",
    "            y.PAINT(BLACK)\n",
    "            p.PAINT(BLACK)\n",
    "            g.PAINT(RED)\n",
    "            new_z = g\n",
    "            self.INSERT_FIXUP(new_z)\n",
    "\n",
    "    def DELETE(self, val):\n",
    "        curNode = self.root\n",
    "        while curNode is not None:\n",
    "            if val < curNode.val:\n",
    "                curNode = curNode.left\n",
    "            elif val > curNode.val:\n",
    "                curNode = curNode.right\n",
    "            else:\n",
    "                # 找到了值为val的元素,正式开始删除\n",
    "\n",
    "                if curNode.left is None and curNode.right is None:\n",
    "                    # case1:curNode为叶子节点：直接删除即可\n",
    "                    if curNode == self.root:\n",
    "                        self.root = None\n",
    "                    else:\n",
    "                        p = curNode.parent\n",
    "                        if curNode == p.left:\n",
    "                            p.left = None\n",
    "                        else:\n",
    "                            p.right = None\n",
    "\n",
    "                elif curNode.left is not None and curNode.right is not None:\n",
    "                    sucNode = self.SUCCESOR(curNode)\n",
    "                    curNode.val, sucNode.val  = sucNode.val, curNode.val\n",
    "                    self.DELETE(sucNode.val)\n",
    "\n",
    "                else:\n",
    "                    p = curNode.parent\n",
    "                    if curNode.left is None:\n",
    "                        x = curNode.right\n",
    "                    else:\n",
    "                        x = curNode.left\n",
    "                    if curNode == p.left:\n",
    "                        p.left = x\n",
    "                    else:\n",
    "                        p.right = x\n",
    "                    x.parent = p\n",
    "                    if curNode.color == BLACK:\n",
    "                        self.DELETE_FIXUP(x)\n",
    "\n",
    "                curNode = None\n",
    "        return False\n",
    "\n",
    "    def DELETE_FIXUP(self, x):\n",
    "        p = x.parent\n",
    "        # w:x的兄弟结点\n",
    "        if x == p.left:\n",
    "            w = x.right\n",
    "        else:\n",
    "            w = x.left\n",
    "\n",
    "        # case1:x的兄弟w是红色的\n",
    "        if w.color == RED:\n",
    "            p.PAINT(RED)\n",
    "            w.PAINT(BLACK)\n",
    "            if w == p.right:\n",
    "                self.LEFT_ROTATE(p)\n",
    "            else:\n",
    "                self.RIGHT_ROTATE(p)\n",
    "\n",
    "        if w.color == BLACK:\n",
    "            # case2:x的兄弟w是黑色的，而且w的两个孩子都是黑色的\n",
    "            if w.left.color == BLACK and w.right.color == BLACK:\n",
    "                w.PAINT(RED)\n",
    "                if p.color == BLACK:\n",
    "                    return\n",
    "                else:\n",
    "                    p.color = BLACK\n",
    "                    self.DELETE_FIXUP(p)\n",
    "\n",
    "            # case3:x的兄弟w是黑色的，而且w的左儿子是红色的，右儿子是黑色的\n",
    "            if w.left.color == RED and w.color == BLACK:\n",
    "                w.left.PAINT(BLACK)\n",
    "                w.PAINT(RED)\n",
    "                self.RIGHT_ROTATE(w)\n",
    "\n",
    "            # case4:x的兄弟w是黑色的，而且w的右儿子是红\n",
    "            if w.right.color == RED:\n",
    "                p.PAINT(BLACK)\n",
    "                w.PAINT(RED)\n",
    "                if w == p.right:\n",
    "                    self.LEFT_ROTATE(p)\n",
    "                else:\n",
    "                    self.RIGHT_ROTATE(p)\n",
    "\n",
    "    def SHOW(self):\n",
    "        self.DISPLAY1(self.root)\n",
    "        return self.zlist\n",
    "\n",
    "    def DISPLAY1(self, node):\n",
    "        if node is None:\n",
    "            return\n",
    "        self.DISPLAY1(node.left)\n",
    "        self.zlist.append(node.val)\n",
    "        self.DISPLAY1(node.right)\n",
    "\n",
    "    def DISPLAY2(self, node):\n",
    "        if node is None:\n",
    "            return\n",
    "        self.DISPLAY2(node.left)\n",
    "        print(node.val)\n",
    "        self.DISPLAY2(node.right)\n",
    "\n",
    "    def DISPLAY3(self, node):\n",
    "        if node is None:\n",
    "            return\n",
    "        self.DISPLAY3(node.left)\n",
    "        self.DISPLAY3(node.right)\n",
    "        print(node.val)\n",
    "\n",
    "class RBTnode:\n",
    "    '''红黑树的节点类型'''\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "\n",
    "    def PAINT(self, color):\n",
    "        self.color = color\n",
    "\n",
    "def zuoxuan(b, c):\n",
    "    a = b.parent\n",
    "    a.left = c\n",
    "    c.parent = a\n",
    "    b.parent = c\n",
    "    c.left = b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK!\n"
     ]
    }
   ],
   "source": [
    "rbt=RBT()\n",
    "b = []\n",
    "\n",
    "for i in range(100):\n",
    "    m = randint(0, 500)\n",
    "    rbt.INSERT(m)\n",
    "    b.append(m)\n",
    "\n",
    "a = rbt.SHOW()\n",
    "b.sort()\n",
    "equal = True\n",
    "for i in range(100):\n",
    "    if a[i] != b[i]:\n",
    "        equal = False\n",
    "        break\n",
    "\n",
    "if not equal:\n",
    "    print('wrong')\n",
    "else:\n",
    "    print('OK!')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
